18 resultados para COMPUTER SCIENCE, THEORY
em Université de Montréal, Canada
Resumo:
La thorie de l'information quantique tudie les limites fondamentales qu'imposent les lois de la physique sur les tches de traitement de donnes comme la compression et la transmission de donnes sur un canal bruit. Cette thse prsente des techniques gnrales permettant de rsoudre plusieurs problmes fondamentaux de la thorie de l'information quantique dans un seul et mme cadre. Le thorme central de cette thse nonce l'existence d'un protocole permettant de transmettre des donnes quantiques que le receveur connat dj partiellement l'aide d'une seule utilisation d'un canal quantique bruit. Ce thorme a de plus comme corollaires immdiats plusieurs thormes centraux de la thorie de l'information quantique. Les chapitres suivants utilisent ce thorme pour prouver l'existence de nouveaux protocoles pour deux autres types de canaux quantiques, soit les canaux de diffusion quantiques et les canaux quantiques avec information supplmentaire fournie au transmetteur. Ces protocoles traitent aussi de la transmission de donnes quantiques partiellement connues du receveur l'aide d'une seule utilisation du canal, et ont comme corollaires des versions asymptotiques avec et sans intrication auxiliaire. Les versions asymptotiques avec intrication auxiliaire peuvent, dans les deux cas, tre considres comme des versions quantiques des meilleurs thormes de codage connus pour les versions classiques de ces problmes. Le dernier chapitre traite d'un phnomne purement quantique appel verrouillage: il est possible d'encoder un message classique dans un tat quantique de sorte qu'en lui enlevant un sous-systme de taille logarithmique par rapport sa taille totale, on puisse s'assurer qu'aucune mesure ne puisse avoir de corrlation significative avec le message. Le message se trouve donc verrouill par une cl de taille logarithmique. Cette thse prsente le premier protocole de verrouillage dont le critre de succs est que la distance trace entre la distribution jointe du message et du rsultat de la mesure et le produit de leur marginales soit suffisamment petite.
Resumo:
La thorie de l'information quantique s'est dveloppe une vitesse fulgurante au cours des vingt dernires annes, avec des analogues et extensions des thormes de codage de source et de codage sur canal bruit pour la communication unidirectionnelle. Pour la communication interactive, un analogue quantique de la complexit de la communication a t dvelopp, pour lequel les protocoles quantiques peuvent performer exponentiellement mieux que les meilleurs protocoles classiques pour certaines tches classiques. Cependant, l'information quantique est beaucoup plus sensible au bruit que l'information classique. Il est donc impratif d'utiliser les ressources quantiques leur plein potentiel. Dans cette thse, nous tudions les protocoles quantiques interactifs du point de vue de la thorie de l'information et tudions les analogues du codage de source et du codage sur canal bruit. Le cadre considr est celui de la complexit de la communication: Alice et Bob veulent faire un calcul quantique biparti tout en minimisant la quantit de communication change, sans gard au cot des calculs locaux. Nos rsultats sont spars en trois chapitres distincts, qui sont organiss de sorte ce que chacun puisse tre lu indpendamment. tant donn le rle central qu'elle occupe dans le contexte de la compression interactive, un chapitre est ddi l'tude de la tche de la redistribution d'tat quantique. Nous prouvons des bornes infrieures sur les cots de communication ncessaires dans un contexte interactif. Nous prouvons galement des bornes atteignables avec un seul message, dans un contexte d'usage unique. Dans un chapitre subsquent, nous dfinissons une nouvelle notion de complexit de l'information quantique. Celle-ci caractrise la quantit d'information, plutt que de communication, qu'Alice et Bob doivent changer pour calculer une tche bipartie. Nous prouvons beaucoup de proprits structurelles pour cette quantit, et nous lui donnons une interprtation oprationnelle en tant que complexit de la communication quantique amortie. Dans le cas particulier d'entres classiques, nous donnons une autre caractrisation permettant de quantifier le cot encouru par un protocole quantique qui oublie de l'information classique. Deux applications sont prsentes: le premier rsultat gnral de somme directe pour la complexit de la communication quantique plus d'une ronde, ainsi qu'une borne optimale, un terme polylogarithmique prs, pour la complexit de la communication quantique avec un nombre de rondes limit pour la fonction ensembles disjoints . Dans un chapitre final, nous initions l'tude de la capacit interactive quantique pour les canaux bruits. tant donn que les techniques pour distribuer de l'intrication sont bien tudies, nous nous concentrons sur un modle avec intrication pralable parfaite et communication classique bruite. Nous dmontrons que dans le cadre plus ardu des erreurs adversarielles, nous pouvons tolrer un taux d'erreur maximal de une demie moins epsilon, avec epsilon plus grand que zro arbitrairement petit, et ce avec un taux de communication positif. Il s'ensuit que les canaux avec bruit alatoire ayant une capacit positive pour la transmission unidirectionnelle ont une capacit positive pour la communication interactive quantique. Nous concluons avec une discussion de nos rsultats et des directions futures pour ce programme de recherche sur une thorie de l'information quantique interactive.
Resumo:
En synthse dimages, reproduire les effets complexes de la lumire sur des matriaux transluminescents, tels que la cire, le marbre ou la peau, contribue grandement au ralisme dune image. Malheureusement, ce ralisme supplmentaire est couteux en temps de calcul. Les modles bass sur la thorie de la diffusion visent rduire ce cot en simulant le comportement physique du transport de la lumire sous surfacique tout en imposant des contraintes de variation sur la lumire incidente et sortante. Une composante importante de ces modles est leur application valuer hirarchiquement lintgrale numrique de lillumination sur la surface dun objet. Cette thse rvise en premier lieu la littrature actuelle sur la simulation raliste de la transluminescence, avant dinvestiguer plus en profondeur leur application et les extensions des modles de diffusion en synthse dimages. Ainsi, nous proposons et valuons une nouvelle technique dintgration numrique hirarchique utilisant une nouvelle analyse frquentielle de la lumire sortante et incidente pour adapter efficacement le taux dchantillonnage pendant lintgration. Nous appliquons cette thorie plusieurs modles qui correspondent ltat de lart en diffusion, octroyant une amlioration possible leur efficacit et prcision.
Resumo:
La synthse d'images dites photoralistes ncessite d'valuer numriquement la manire dont la lumire et la matire interagissent physiquement, ce qui, malgr la puissance de calcul impressionnante dont nous bnficions aujourd'hui et qui ne cesse d'augmenter, est encore bien loin de devenir une tche triviale pour nos ordinateurs. Ceci est d en majeure partie la manire dont nous reprsentons les objets: afin de reproduire les interactions subtiles qui mnent la perception du dtail, il est ncessaire de modliser des quantits phnomnales de gomtries. Au moment du rendu, cette complexit conduit inexorablement de lourdes requtes d'entres-sorties, qui, couples des valuations d'oprateurs de filtrage complexes, rendent les temps de calcul ncessaires produire des images sans dfaut totalement draisonnables. Afin de pallier ces limitations sous les contraintes actuelles, il est ncessaire de driver une reprsentation multichelle de la matire. Dans cette thse, nous construisons une telle reprsentation pour la matire dont l'interface correspond une surface perturbe, une configuration qui se construit gnralement via des cartes d'lvations en infographie. Nous drivons notre reprsentation dans le contexte de la thorie des microfacettes (conue l'origine pour modliser la rflectance de surfaces rugueuses), que nous prsentons d'abord, puis augmentons en deux temps. Dans un premier temps, nous rendons la thorie applicable travers plusieurs chelles d'observation en la gnralisant aux statistiques de microfacettes dcentres. Dans l'autre, nous drivons une procdure d'inversion capable de reconstruire les statistiques de microfacettes partir de rponses de rflexion d'un matriau arbitraire dans les configurations de rtrorflexion. Nous montrons comment cette thorie augmente peut tre exploite afin de driver un oprateur gnral et efficace de rchantillonnage approximatif de cartes d'lvations qui (a) prserve l'anisotropie du transport de la lumire pour n'importe quelle rsolution, (b) peut tre appliqu en amont du rendu et stock dans des MIP maps afin de diminuer drastiquement le nombre de requtes d'entres-sorties, et (c) simplifie de manire considrable les oprations de filtrage par pixel, le tout conduisant des temps de rendu plus courts. Afin de valider et dmontrer l'efficacit de notre oprateur, nous synthtisons des images photoralistes anticreneles et les comparons des images de rfrence. De plus, nous fournissons une implantation C++ complte tout au long de la dissertation afin de faciliter la reproduction des rsultats obtenus. Nous concluons avec une discussion portant sur les limitations de notre approche, ainsi que sur les verrous restant lever afin de driver une reprsentation multichelle de la matire encore plus gnrale.
Resumo:
Un certain nombre de thories pdagogiques ont t tablies depuis plus de 20 ans. Elles font appel aux ractions de lapprenant en situation dapprentissage, mais aucune thorie pdagogique na pu dcrire compltement un processus denseignement en tenant compte de toutes les ractions motionnelles de lapprenant. Nous souhaitons intgrer les motions de lapprenant dans ces processus dapprentissage, car elles sont importantes dans les mcanismes dacquisition de connaissances et dans la mmorisation. Rcemment on a vu que le facteur motionnel est considr jouer un rle trs important dans les processus cognitifs. Modliser les ractions motionnelles dun apprenant en cours du processus dapprentissage est une nouveaut pour un Systme Tutoriel Intelligent. Pour raliser notre recherche, nous examinerons les thories pdagogiques qui nont pas considr les motions de lapprenant. Jusqu maintenant, aucun Systme Tutoriel Intelligent destin lenseignement na incorpor la notion de facteur motionnel pour un apprenant humain. Notre premier objectif est danalyser quelques stratgies pdagogiques et de dtecter les composantes motionnelles qui peuvent y tre ou non. Nous cherchons dterminer dans cette analyse quel type de mthode didactique est utilis, autrement dit, que fait le tuteur pour prvoir et aider lapprenant accomplir sa tche dapprentissage dans des conditions optimales. Le deuxime objectif est de proposer lamlioration de ces mthodes en ajoutant les facteurs motionnels. On les nommera des mthodes motionnelles . Le dernier objectif vise exprimenter le modle dune thorie pdagogique amliore en ajoutant les facteurs motionnels. Dans le cadre de cette recherche nous analyserons un certain nombre de thories pdagogiques, parmi lesquelles les thories de Robert Gagn, Jerome Bruner, Herbert J. Klausmeier et David Merrill, pour chercher identifier les composantes motionnelles. Aucune thorie pdagogique na mis laccent sur les motions au cours du processus dapprentissage. Ces thories pdagogiques sont dveloppes en tenant compte de plusieurs facteurs externes qui peuvent influencer le processus dapprentissage. Nous proposons une approche base sur la prdiction dmotions qui est lie de potentielles causes dclenches par diffrents facteurs dterminants au cours du processus dapprentissage. Nous voulons dvelopper une technique qui permette au tuteur de traiter la raction motionnelle de lapprenant un moment donn au cours de son processus dapprentissage et de linclure dans une mthode pdagogique. Pour atteindre le deuxime objectif de notre recherche, nous utiliserons un module tuteur apprenant bas sur le principe de lducation des motions de lapprenant, modle qui vise premirement sa personnalit et deuximement ses connaissances. Si on dfini lapprenant, on peut prdire ses ractions motionnelles (positives ou ngatives) et on peut sassurer de la bonne disposition de lapprenant, de sa coopration, sa communication et loptimisme ncessaires rgler les problmes motionnels. Pour atteindre le troisime objectif, nous proposons une technique qui permet au tuteur de rsoudre un problme de raction motionnelle de lapprenant un moment donn du processus dapprentissage. Nous appliquerons cette technique une thorie pdagogique. Pour cette premire thorie, nous tudierons leffet produit par certaines stratgies pdagogiques dun tuteur virtuel au sujet de ltat motionnel de lapprenant, et pour ce faire, nous dvelopperons une structure de donnes en ligne quun agent tuteur virtuel peut induire lapprenant des motions positives. Nous analyserons les rsultats exprimentaux en utilisant la premire thorie et nous les comparerons ensuite avec trois autres thories que nous avons proposes dtudier. En procdant de la sorte, nous atteindrons le troisime objectif de notre recherche, celui dexprimenter un modle dune thorie pdagogique et de le comparer ensuite avec dautres thories dans le but de dvelopper ou damliorer les mthodes motionnelles. Nous analyserons les avantages, mais aussi les insuffisances de ces thories par rapport au comportement motionnel de lapprenant. En guise de conclusion de cette recherche, nous retiendrons de meilleures thories pdagogiques ou bien nous suggrerons un moyen de les amliorer.
Resumo:
Cette thse est consacre la complexit base sur le paradigme des preuves interactives. Les classes ainsi dfinies ont toutes en commun quun ou plusieurs prouveurs, infiniment puissants, tentent de convaincre un vrificateur, de puissance borne, de lappartenance dun mot un langage. Nous abordons ici le modle classique, o les participants sont des machines de Turing, et le modle quantique, o ceux-ci sont des circuits quantiques. La revue de littrature que comprend cette thse sadresse un lecteur dj familier avec la complexit et linformatique quantique. Cette thse prsente comme rsultat la caractrisation de la classe NP par une classe de preuves interactives quantiques de taille logarithmique. Les diffrentes classes sont prsentes dans un ordre permettant daborder aussi facilement que possible les classes interactives. Le premier chapitre est consacr aux classes de base de la complexit ; celles-ci seront utiles pour situer les classes subsquemment prsentes. Les chapitres deux et trois prsentent respectivement les classes un et plusieurs prouveurs. La prsentation du rsultat ci-haut mentionn est lobjet du chapitre quatre.
Resumo:
Depuis lintroduction de la mcanique quantique, plusieurs mystres de la nature ont trouv leurs explications. De plus en plus, les concepts de la mcanique quantique se sont entremls avec dautres de la thorie de la complexit du calcul. De nouvelles ides et solutions ont t dcouvertes et labores dans le but de rsoudre ces problmes informatiques. En particulier, la mcanique quantique a secou plusieurs preuves de scurit de protocoles classiques. Dans ce memoire, nous faisons un talage de rsultats rcents de limplication de la mcanique quantique sur la complexit du calcul, et cela plus prcisment dans le cas de classes avec interaction. Nous prsentons ces travaux de recherches avec la nomenclature des jeux information imparfaite avec coopration. Nous exposons les diffrences entre les thories classiques, quantiques et non-signalantes et les dmontrons par lexemple du jeu cycle impair. Nous centralisons notre attention autour de deux grands thmes : leffet sur un jeu de lajout de joueurs et de la rptition parallle. Nous observons que leffet de ces modifications a des consquences trs diffrentes en fonction de la thorie physique considre.
Resumo:
Dans le dveloppement logiciel en industrie, les documents de spcification jouent un rle important pour la communication entre les analystes et les dveloppeurs. Cependant, avec le temps, les changements de personel et les chances toujours plus courtes, ces documents sont souvent obsoltes ou incohrents avec l'tat effectif du systme, i.e., son code source. Pourtant, il est ncessaire que les composants du systme logiciel soient conservs jour et cohrents avec leurs documents de spcifications pour faciliter leur dveloppement et maintenance et, ainsi, pour en rduire les cots. Maintenir la cohrence entre spcification et code source ncessite de pouvoir reprsenter les changements sur les uns et les autres et de pouvoir appliquer ces changements de manire cohrente et automatique. Nous proposons une solution permettant de dcrire une reprsentation d'un logiciel ainsi qu'un formalisme mathmatique permettant de dcrire et de manipuler l'volution des composants de ces reprsentations. Le formalisme est bas sur les triplets de Hoare pour reprsenter les transformations et sur la thorie des groupes et des homomorphismes de groupes pour manipuler ces transformations et permettrent leur application sur les diffrentes reprsentations du systme. Nous illustrons notre formalisme sur deux reprsentations d'un systme logiciel : PADL, une reprsentation architecturale de haut niveau (semblable UML), et JCT, un arbre de syntaxe abstrait bas sur Java. Nous dfinissons galement des transformations reprsentant l'volution de ces reprsentations et la transposition permettant de reporter les transformations d'une reprsentation sur l'autre. Enfin, nous avons dvelopp et dcrivons brivement une implmentation de notre illustration, un plugiciel pour l'IDE Eclipse dtectant les transformations effectues sur le code par les dveloppeurs et un gnrateur de code pour l'intgration de nouvelles reprsentations dans l'implmentation.
Resumo:
Lannotation en rles smantiques est une tche qui permet dattribuer des tiquettes de rles telles que Agent, Patient, Instrument, Lieu, Destination etc. aux diffrents participants actants ou circonstants (arguments ou adjoints) dune lexie prdicative. Cette tche ncessite des ressources lexicales riches ou des corpus importants contenant des phrases annotes manuellement par des linguistes sur lesquels peuvent sappuyer certaines approches dautomatisation (statistiques ou apprentissage machine). Les travaux antrieurs dans ce domaine ont port essentiellement sur la langue anglaise qui dispose de ressources riches, telles que PropBank, VerbNet et FrameNet, qui ont servi alimenter les systmes dannotation automatiss. Lannotation dans dautres langues, pour lesquelles on ne dispose pas dun corpus annot manuellement, repose souvent sur le FrameNet anglais. Une ressource telle que FrameNet de langlais est plus que ncessaire pour les systmes dannotation automatis et lannotation manuelle de milliers de phrases par des linguistes est une tche fastidieuse et exigeante en temps. Nous avons propos dans cette thse un systme automatique pour aider les linguistes dans cette tche qui pourraient alors se limiter la validation des annotations proposes par le systme. Dans notre travail, nous ne considrons que les verbes qui sont plus susceptibles que les noms dtre accompagns par des actants raliss dans les phrases. Ces verbes concernent les termes de spcialit dinformatique et dInternet (ex. accder, configurer, naviguer, tlcharger) dont la structure actancielle est enrichie manuellement par des rles smantiques. La structure actancielle des lexies verbales est dcrite selon les principes de la Lexicologie Explicative et Combinatoire, LEC de Meluk et fait appel partiellement (en ce qui concerne les rles smantiques) la notion de Frame Element tel que dcrit dans la thorie Frame Semantics (FS) de Fillmore. Ces deux thories ont ceci de commun quelles mnent toutes les deux la construction de dictionnaires diffrents de ceux issus des approches traditionnelles. Les lexies verbales dinformatique et dInternet qui ont t annotes manuellement dans plusieurs contextes constituent notre corpus spcialis. Notre systme qui attribue automatiquement des rles smantiques aux actants est bas sur des rgles ou classificateurs entrans sur plus de 2300 contextes. Nous sommes limits une liste de rles restreinte car certains rles dans notre corpus nont pas assez dexemples annots manuellement. Dans notre systme, nous navons trait que les rles Patient, Agent et Destination dont le nombre dexemple est suprieur 300. Nous avons cre une classe que nous avons nomm Autre o nous avons rassembl les autres rles dont le nombre dexemples annots est infrieur 100. Nous avons subdivis la tche dannotation en sous-tches : identifier les participants actants et circonstants et attribuer des rles smantiques uniquement aux actants qui contribuent au sens de la lexie verbale. Nous avons soumis les phrases de notre corpus lanalyseur syntaxique Syntex afin dextraire les informations syntaxiques qui dcrivent les diffrents participants dune lexie verbale dans une phrase. Ces informations ont servi de traits (features) dans notre modle dapprentissage. Nous avons propos deux techniques pour lidentification des participants : une technique base de rgles o nous avons extrait une trentaine de rgles et une autre technique base sur lapprentissage machine. Ces mmes techniques ont t utilises pour la tche de distinguer les actants des circonstants. Nous avons propos pour la tche dattribuer des rles smantiques aux actants, une mthode de partitionnement (clustering) semi supervis des instances que nous avons compare la mthode de classification de rles smantiques. Nous avons utilis CHAMLON, un algorithme hirarchique ascendant.
Resumo:
Dans ce mmoire, je dmontre que la distribution de probabilits de l'tat quantique Greenberger-Horne-Zeilinger (GHZ) sous l'action locale de mesures de von Neumann indpendantes sur chaque qubit suit une distribution qui est une combinaison convexe de deux distributions. Les coefficients de la combinaison sont relis aux parties quatoriales des mesures et les distributions associes ces coefficients sont relies aux parties relles des mesures. Une application possible du rsultat est qu'il permet de scinder en deux la simulation de l'tat GHZ. Simuler, en pire cas ou en moyenne, un tat quantique comme GHZ avec des ressources alatoires, partages ou prives, et des ressources classiques de communication, ou mme des ressources fantaisistes comme les botes non locales, est un problme important en complexit de la communication quantique. On peut penser ce problme de simulation comme un problme o plusieurs personnes obtiennent chacune une mesure de von Neumann appliquer sur le sous-systme de l'tat GHZ qu'il partage avec les autres personnes. Chaque personne ne connat que les donnes dcrivant sa mesure et d'aucune faon une personne ne connat les donnes dcrivant la mesure d'une autre personne. Chaque personne obtient un rsultat alatoire classique. La distribution conjointe de ces rsultats alatoires classiques suit la distribution de probabilits trouve dans ce mmoire. Le but est de simuler classiquement la distribution de probabilits de l'tat GHZ. Mon rsultat indique une marche suivre qui consiste d'abord simuler les parties quatoriales des mesures pour pouvoir ensuite savoir laquelle des distributions associes aux parties relles des mesures il faut simuler. D'autres chercheurs ont trouv comment simuler les parties quatoriales des mesures de von Neumann avec de la communication classique dans le cas de 3 personnes, mais la simulation des parties relles rsiste encore et toujours.
Resumo:
Partant des travaux sminaux de Boole, Frege et Russell, le mmoire cherche clarifier lenjeu du pluralisme logique lre de la prolifration des logiques non-classiques et des dveloppements en informatique thorique et en thorie des preuves. Deux chapitres plus historiques sont lordre du jour : (1) le premier chapitre articule labsolutisme de Frege et Russell en prenant soin de montrer comment il exclut la possibilit denvisager des structures et des logiques alternatives; (2) le quatrime chapitre expose le chemin qui mena Carnap ladoption de la mthode syntaxique et du principe de tolrance, pour ensuite dgager linstrumentalisme carnapien en philosophie de la Logique et des mathmatiques. Passant par lanalyse dune interprtation intuitive de la logique linaire, le deuxime chapitre se tourne ensuite vers ltablissement dune forme logico-mathmatique de pluralisme logique laide de la thorie des relations dordre et la thorie des catgories. Le troisime chapitre dlimite le terrain de jeu des positions entourant le dbat entre monisme et pluralisme puis offre un argument contre la thse qui veut que le conflit entre logiques rivales soit apparent, le tout grce lutilisation du point de vue des logiques sous-structurelles. Enfin, le cinquime chapitre dmontre que chacune des trois grandes approches au concept de consquence logique (modle-thortique, preuve-thortique et dialogique) forme un cadre suffisamment gnral pour tablir un pluralisme. Bref, le mmoire est une dfense du pluralisme logique.
Resumo:
Thse numrise par la Division de la gestion de documents et des archives de l'Universit de Montral
Resumo:
Un objectif principal du gnie logiciel est de pouvoir produire des logiciels complexes, de grande taille et fiables en un temps raisonnable. La technologie oriente objet (OO) a fourni de bons concepts et des techniques de modlisation et de programmation qui ont permis de dvelopper des applications complexes tant dans le monde acadmique que dans le monde industriel. Cette exprience a cependant permis de dcouvrir les faiblesses du paradigme objet (par exemples, la dispersion de code et le problme de traabilit). La programmation oriente aspect (OA) apporte une solution simple aux limitations de la programmation OO, telle que le problme des proccupations transversales. Ces proccupations transversales se traduisent par la dispersion du mme code dans plusieurs modules du systme ou lemmlement de plusieurs morceaux de code dans un mme module. Cette nouvelle mthode de programmer permet dimplmenter chaque problmatique indpendamment des autres, puis de les assembler selon des rgles bien dfinies. La programmation OA promet donc une meilleure productivit, une meilleure rutilisation du code et une meilleure adaptation du code aux changements. Trs vite, cette nouvelle faon de faire sest vue stendre sur tout le processus de dveloppement de logiciel en ayant pour but de prserver la modularit et la traabilit, qui sont deux proprits importantes des logiciels de bonne qualit. Cependant, la technologie OA prsente de nombreux dfis. Le raisonnement, la spcification, et la vrification des programmes OA prsentent des difficults dautant plus que ces programmes voluent dans le temps. Par consquent, le raisonnement modulaire de ces programmes est requis sinon ils ncessiteraient dtre rexamins au complet chaque fois quun composant est chang ou ajout. Il est cependant bien connu dans la littrature que le raisonnement modulaire sur les programmes OA est difficile vu que les aspects appliqus changent souvent le comportement de leurs composantes de base [47]. Ces mmes difficults sont prsentes au niveau des phases de spcification et de vrification du processus de dveloppement des logiciels. Au meilleur de nos connaissances, la spcification modulaire et la vrification modulaire sont faiblement couvertes et constituent un champ de recherche trs intressant. De mme, les interactions entre aspects est un srieux problme dans la communaut des aspects. Pour faire face ces problmes, nous avons choisi dutiliser la thorie des catgories et les techniques des spcifications algbriques. Pour apporter une solution aux problmes ci-dessus cits, nous avons utilis les travaux de Wiels [110] et dautres contributions telles que celles dcrites dans le livre [25]. Nous supposons que le systme en dveloppement est dj dcompos en aspects et classes. La premire contribution de notre thse est lextension des techniques des spcifications algbriques la notion daspect. Deuximement, nous avons dfini une logique, LA , qui est utilise dans le corps des spcifications pour dcrire le comportement de ces composantes. La troisime contribution consiste en la dfinition de loprateur de tissage qui correspond la relation dinterconnexion entre les modules daspect et les modules de classe. La quatrime contribution concerne le dveloppement dun mcanisme de prvention qui permet de prvenir les interactions indsirables dans les systmes orients aspect.
Resumo:
Nous introduisons un nouveau modle de la communication deux parties dans lequel nous nous intressons au temps que prennent deux participants effectuer une tche travers un canal avec dlai d. Nous tablissons quelques bornes suprieures et infrieures et comparons ce nouveau modle aux modles de communication classiques et quantiques tudis dans la littrature. Nous montrons que la complexit de la communication dune fonction sur un canal avec dlai est borne suprieurement par sa complexit de la communication modulo un facteur multiplicatif d/ lg d. Nous prsentons ensuite quelques exemples de fonctions pour lesquelles une stratgie astucieuse se servant du temps mort confre un avantage sur une implmentation nave dun protocole de communication optimal en terme de complexit de la communication. Finalement, nous montrons quun canal avec dlai permet de raliser un change de bit cryptographique, mais que, par lui-mme, est insufsant pour raliser la primitive cryptographique de transfert quivoque.
Resumo:
Dans ce mmoire, nous nous pencherons tout particulirement sur une primitive cryptographique connue sous le nom de partage de secret. Nous explorerons autant le domaine classique que le domaine quantique de ces primitives, couronnant notre tude par la prsentation dun nouveau protocole de partage de secret quantique ncessitant un nombre minimal de parts quantiques c.--d. une seule part quantique par participant. Louverture de notre tude se fera par la prsentation dans le chapitre prliminaire dun survol des notions mathmatiques sous-jacentes la thorie de linformation quantique ayant pour but primaire dtablir la notation utilise dans ce manuscrit, ainsi que la prsentation dun prcis des proprits mathmatique de ltat de Greenberger-Horne-Zeilinger (GHZ) frquemment utilis dans les domaines quantiques de la cryptographie et des jeux de la communication. Mais, comme nous lavons mentionn plus haut, cest le domaine cryptographique qui restera le point focal de cette tude. Dans le second chapitre, nous nous intresserons la thorie des codes correcteurs derreurs classiques et quantiques qui seront leur tour dextrme importances lors de lintroduction de la thorie quantique du partage de secret dans le chapitre suivant. Dans la premire partie du troisime chapitre, nous nous concentrerons sur le domaine classique du partage de secret en prsentant un cadre thorique gnral portant sur la construction de ces primitives illustrant tout au long les concepts introduits par des exemples prsents pour leurs intrts autant historiques que pdagogiques. Ceci prparera le chemin pour notre expos sur la thorie quantique du partage de secret qui sera le focus de la seconde partie de ce mme chapitre. Nous prsenterons alors les thormes et dfinitions les plus gnraux connus date portant sur la construction de ces primitives en portant un intrt particulier au partage quantique seuil. Nous montrerons le lien troit entre la thorie quantique des codes correcteurs derreurs et celle du partage de secret. Ce lien est si troit que lon considre les codes correcteurs derreurs quantiques taient de plus proches analogues aux partages de secrets quantiques que ne leur taient les codes de partage de secrets classiques. Finalement, nous prsenterons un de nos trois rsultats parus dans A. Broadbent, P.-R. Chouha, A. Tapp (2009); un protocole scuritaire et minimal de partage de secret quantique a seuil (les deux autres rsultats dont nous traiterons pas ici portent sur la complexit de la communication et sur la simulation classique de ltat de GHZ).
